package Leetcode.StackAndQueue.trapWater42;

import java.util.Stack;

/**
 * 单调栈
 * https://leetcode-cn.com/problems/trapping-rain-water/solution/trapping-rain-water-by-ikaruga/
 *0,1,0,2,1,0,1,3,2,1,2,1
 * 先将0 入栈 1大于0 将0出栈 发现栈空了 说明这一列体积算不了为0  事实上也是0  所以break
 * 将1 入栈 再将0 入栈 2大于0 0出栈并且计算0这一列装的水 算法是当前遍历到2的下标1 减去 栈顶的下标 加一算的宽 再取这两个值的
 * 最小值减去该列本身的体积 就得到这列的水 累加到结果里
 * 2仍然大于1  1出栈 结果break
 * 2入栈 1 0 分别入栈 1大于0 0 出栈算的体积 继续遍历3大于栈中所有元素再分别将 1 1 2出栈
 * 3入栈 接着 2 1入栈  2 大于栈顶的1 计算1该列的体积 再将末尾1入栈
 * 栈中最后3221 虽然非空 运算结束
 */
public class Solution2 {
    public int trap(int[] height) {
        int result = 0;
        int len = height.length;
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while(i < len) {
            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int h = height[stack.pop()];
                //此处的if是判断栈是否空 若为空则计算到最后一根柱子所在列的水 很显然是为0的所以break
                if(stack.isEmpty()) {
                    break;
                }
                int dis = i - stack.peek() - 1;
                int min = Math.min(height[stack.peek()],height[i]);
                result += dis * (min - h);
            }
            stack.push(i);
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
        Solution2 solution = new Solution2();
        System.out.println(solution.trap(nums));
    }
}
